package trees;

import beans.TreeNode;

/**
 * @author pengfei.hpf
 * @date 2020/3/5
 * @verdion 1.0.0
 *
 * 给你一棵指定的二叉树，请你计算它最长连续序列路径的长度。
 *
 * 该路径，可以是从某个初始结点到树中任意结点，通过「父 - 子」关系连接而产生的任意路径。
 *
 * 这个最长连续的路径，必须从父结点到子结点，反过来是不可以的。
 *
 * 示例 1：
 *
 * 输入:
 *
 *    1
 *     \
 *      3
 *     / \
 *    2   4
 *         \
 *          5
 *
 * 输出: 3
 *
 * 解析: 当中，最长连续序列是 3-4-5，所以返回结果为 3
 * 示例 2：
 *
 * 输入:
 *
 *    2
 *     \
 *      3
 *     /
 *    2
 *   /
 *  1
 *
 * 输出: 2
 *
 * 解析: 当中，最长连续序列是 2-3。注意，不是 3-2-1，所以返回 2。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-longest-consecutive-sequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LongestConsecutive {
    private int max = 0;
    public int longestConsecutive(TreeNode root){
        if(root == null){
            return 0;
        }
        find(root, 0, 0);

        return max;
    }

    private void find(TreeNode root, int parent, int count){

        if(count != 0 && root.val == parent +1){
            count ++;
        } else {
            count = 1;
        }
        if(count > max){
            max = count;
        }
        if(root.left != null){
            find(root.left, root.val, count);
        }
        if(root.right != null){
            find(root.right, root.val, count);
        }

    }
}
